//260. 只出现一次的数字 III
//思路：先将所有数字进行异或，这样就得出两个单身狗数异或的结果
//再将结果依次右移，记下第一个为1的位置pos（异或的规则：相同为0，相异为1）
//再将每个数据按pos为1或为0，分为两组分别异或处理
//最后得出的就是两个只出现过一次的数字

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> v;

        int tmp = 0;
        for(auto e : nums)
        {
            tmp ^= e;
        }

        //找到二进制中第一个1的位置
        int pos = 0;
        for(int i = 0; i < 32; ++i)
        {
            if(((tmp>>i)&1) == 1)
            {
                pos = i;
                break;
            }
        }

        //对pos位置为1或非1的数据分别异或
        int x = 0, y = 0;
        for(auto e : nums)
        {
            if(((e>>pos)&1) == 1)
            {
                x ^= e;
            }
            else
            {
                y ^= e;
            }
        }
        v.push_back(x);
        v.push_back(y);

        return v;
    }
};